import java.util.*;

public class BTree {

    private Node root = null;
    private int count = 0;
    private int maxdepth = 0;

    public BTree() {
	Random rmax = new Random();
	rmax.setSeed((long)rmax.nextInt());
	maxdepth = rmax.nextInt(5) + 2;
	System.out.println("maxdepth: "+maxdepth);   
	root = null;
    }

    public BTree(Node rootNode) {
	Random rmax = new Random();
	rmax.setSeed((long)rmax.nextInt());
	maxdepth = rmax.nextInt(5) + 2;
	System.out.println("maxdepth: "+maxdepth);
	root = rootNode;
    }

    public BTree(Node rootNode, BTree leftTree, BTree rightTree) {
	root = rootNode;
	int l, r;
	if((l = leftTree.getMaxdepth()) >= (r = rightTree.getMaxdepth())) {
	    maxdepth = l + 1;
	}
	else {
	    maxdepth = r + 1;
	}
	insertLeftTree(leftTree);
	insertRightTree(rightTree);
    }

    public BTree(BTree tree) {
	root = tree.getRoot();
	maxdepth = tree.getMaxdepth();
    }

    public void setRoot (Node rnode) {
	root = rnode;	
    }
    
    public Node getRoot () {
	return root;	
    }

    public int getMaxdepth() {
	return maxdepth;
    }

    public boolean isEmpty() {
	if(root == null)
	    return true;
	else
	    return false;
    }
  
    public void copyTree(Node tree, Node newTree) {
	if (tree != null)
	    {  // copy node
		newTree = new Node(tree.getKey());
		if (newTree == null)   {
		    System.out.println("TreeException: Cannot allocate memory");
		    System.exit(1);
		}
		
		copyTree(tree.getLeft(), newTree.getLeft());
		copyTree(tree.getRight(), newTree.getRight());
	    }
	else
	    newTree = null; // copy empty tree
    }
    
    public void insertLeft(Item leftItem) {

	if (isEmpty()) {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else if (root.getLeft() != null)     {
	    System.out.println("TreeException: Cannot overwrite left subtree");
	    System.exit(1);
	}
	else // Assertion: nonempty tree; no left child
	    {  
		root.setLeft(new Node(leftItem, null, null));
		if (root.getLeft() == null) {
		    System.out.println("TreeException: Cannot allocate memory");
		    System.exit(1);
		}
	    }
    }
    
    public void insertRight(Item rightItem) {
	if (isEmpty()) {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else if (root.getRight() != null)   {
	    System.out.println("TreeException: Cannot overwrite right subtree");
	    System.exit(1);
	}
	else // Assertion: nonempty tree; no right child
	    {  
		root.setRight(new Node(rightItem, null, null));
		if (root.getRight() == null)   {
		    System.out.println("TreeException: Cannot allocate memory");
		    System.exit(1);
		}
	    } // end if
    }

    public void insertLeftTree (BTree leftTree) {
	if (isEmpty())       {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else if (root.getLeft() != null)    {
	    System.out.println("TreeException: Cannot overwrite left subtree");
	    System.exit(1);
	}
	else // Assertion: nonempty tree; no left child
	    {  
		root.setLeft(leftTree.getRoot());
		leftTree.setRoot(null);
	    }
    }
    
    public void removeLeftTree (BTree leftTree) {
	if (isEmpty())    {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else
	    {  
		leftTree = new BTree(root.getLeft());
		root.setLeft(null);
	    } // end if
    }
    
    public void insertRightTree (BTree rightTree) {
	if (isEmpty())  {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else if (root.getRight() != null)  {
	    System.out.println("TreeException: Cannot overwrite right subtree");
	    System.exit(1);
	}
	else // Assertion: nonempty tree; no right child
	    {  
		root.setRight(rightTree.getRoot());
		rightTree.setRoot(null);
	    } // end if
    }
    
    public void removeRightTree (BTree rightTree) {
	if (isEmpty())      {
	    System.out.println("TreeException: Empty tree");
	    System.exit(1);
	}
	else
	    {  
		rightTree = new BTree(root.getRight());
		System.out.println("right size: "+rightTree.getSize());
		root.setRight(null);
	    } // end if
    }
    
    public BTree getLeftTree() {
	Node leftTree = null;
	if (isEmpty())
	    return (new BTree());
	else
	    {  
		copyTree(root.getLeft(), leftTree);
		return (new BTree(leftTree));
	    } // end if
    }

    public BTree getRightTree() {
	Node rightTree = null;
	if (isEmpty())
	    return (new BTree());
	else
	    {  
		copyTree(root.getRight(), rightTree);
		return (new BTree(rightTree));
	    } // end if
    }


    public int getSize() {
	count = 0;
	return size(root);
    }

    public int getHeight() {
	double d1 = 0.0, d2 = 0.0;
	return height(root, d1, d2);
    }

    
    public void initGrow(int depth) {
	root = initGrow(root, depth);
    }

    public void initFull(int depth) {
	root = initFull(root, depth);
    }

    public void display (Node rootNode) {
	if(rootNode != null)
	    {
		display(rootNode.getLeft());
		rootNode.getKey().printNode();
		display(rootNode.getRight());
	    }
    }

    public void destroyBTree() {
	root = destroyBTree(root);
	root = null;
    }

    private Node destroyBTree(Node tree) {
	if(tree != null){
	    tree.setLeft(destroyBTree(tree.getLeft()));
	    tree.setRight(destroyBTree(tree.getRight()));
	    tree = null;
	}
	return tree;
    }

    private int size(Node rootNode) {
	if(rootNode != null)
	    {
		size(rootNode.getLeft());
		count++;
		size(rootNode.getRight());
	    }
	    return count;
    }

    private int height(Node rootNode, double d1, double d2) {
	if(rootNode == null)
	    return 0;
	d1 = (double)height(rootNode.getLeft(), d1, d2);
	d2 = (double)height(rootNode.getRight(), d1, d2);
	return ((int)Math.max(d1, d2)+1);
    }

    private Node getRandomNode() {
	int nIndex;
	Random rand = new Random();
	rand.setSeed((long)rand.nextInt());
	nIndex = rand.nextInt(4);
	if(nIndex == 0)
	    {
		return (new Node(new Item('+')));
	    }
	else if(nIndex == 1)
	    {
		return (new Node(new Item('-')));
	    }
	else if(nIndex == 2)
	    {
		return (new Node(new Item('*')));
	    }
	else if(nIndex == 3)
	    {
		return (new Node(new Item('/')));
	    }
	else
	    {
		System.out.println("Error creating random node");
		System.exit(1);
	    }
	return null;
    }

    private Node getRandomNode(Node rnode, int pos) {

	if (pos == 1)
	    {
		//rnode.setLeft(new Node(new Item(rval)));
		return rnode.getLeft();
	    }
	else if(pos == 2)
	    {
		//rnode.setRight(new Node(new Item(rval)));
		return rnode.getRight();
	    }
	else
	    {
		System.out.println("Wrong position");
		System.exit(1);
	    }
	return null;
    }

    private Node getRandomNodeLeaf() {
	Random rand = new Random();
	rand.setSeed((long)rand.nextInt());
	double dv = rand.nextDouble();
	//double rval = rand.nextInt() * dv;
	//return (new Node(new Item(rval)));
	if(Math.abs(dv) > 0.3)
	    {
		double rval = rand.nextInt(100) * dv;
		return (new Node(new Item(rval)));
	    }
	else
	    {
		return (new Node(new Item(1)));
		}
    }

    private Node initGrow(Node rnode, int depth) {
	if(depth == 1)
	    {
		rnode = getRandomNode();
	    }
	else if(depth == maxdepth)
	    {
		rnode = getRandomNodeLeaf();
	    }
	else
	    {
		Random rand = new Random();
		rand.setSeed((long)rand.nextInt());
		if(Math.abs(rand.nextDouble()) > 0.5)
		    {
			rnode = getRandomNode();
		    }
		else
		    {
			rnode = getRandomNodeLeaf();
		    }
	    }
	
	if(rnode.getKey().getNodeType() == 2)
	    {
		rnode.setLeft(initGrow(rnode.getLeft(), depth+1));
		rnode.setRight(initGrow(rnode.getRight(), depth+1));
	    }
	return rnode;
    }

    private Node initFull(Node rnode, int depth) {
	if(depth < maxdepth)
	    {
		rnode = getRandomNode();
		rnode.setLeft(initFull(rnode.getLeft(), depth+1));
		rnode.setRight(initFull(rnode.getRight(), depth+1));
	    }
	else
	    {
		rnode = getRandomNodeLeaf();
	    }
	return rnode;
    }

    public double getFitness(TrainingData td) {
	int trainingSize = td.getTrainingSize();
	double fitnessindex = 0.0;
	for(int i=0; i < trainingSize; i++) {
	    double x = td.getXsetValue(i);
	    double y = td.getFunctionValue(i);
	    double fx = evaluateTree(root, x);
	    fitnessindex += Math.abs(fx - y);
	    System.out.println("x y fx fitness "+x+" "+y+" "+fx+" "+fitnessindex);
	}
	return fitnessindex;
    }

    public double evaluateTree(Node tn, double x) {
	
	if(tn == null) {
	    System.out.println("here ");
	    return 0.0;
	}

	
	
	if(tn.getKey().getNodeType() == 0)
	    return tn.getKey().getRandom();
	if(tn.getKey().getNodeType() == 1)
	    return x;
	
	if(tn.getKey().getNodeType() == 2) {
	    double d1 = evaluateTree(tn.getLeft(), x);
	    double d2 = evaluateTree(tn.getRight(), x);
	    if(tn.getKey().getOperator() == '+')
		return (d1 + d2);
	    else if(tn.getKey().getOperator() == '-')
		return (d1 - d2);
	    else if(tn.getKey().getOperator() == '*')
		return (d1 * d2);
	    else if(tn.getKey().getOperator() == '/'){
		if(d2 != 0.0)
		    return (d1 / d2);
		else {
		    //destroyBTree();
		    return 0.0;
		}
	    }
	    else {
		System.out.println("Wrong operator");
		return 0.0;
	    }
	}
	return 0.0;
    }
    
}
